Storage systems, such as solid state drives (SSDs) including NAND flash memory, are commonly used in electronic systems ranging from consumer products to enterprise-level computer systems. The market for SSDs has increased and its acceptance for use by private enterprises or government agencies to store data is becoming more widespread. SSDs and similar storage devices utilizing block-oriented architectures share a common issue: the need to create space for writing new data by collecting sparsely distributed data into a smaller number of blocks. This process is referred to as “garbage collection”. The need for garbage collection in many block-oriented storage devices is generally due to the inability to write in place to memory, and the mismatch between write granularity and erase granularity in those storage device.
The garbage collection process may introduce a significant burden on processing resources which, in turn, may reduce SSD performance. Garbage collection involves reading valid data from a block of non-volatile memory that is to be reused and writing it back to a new block. In many SSDs there is an additional burden to evaluate which data within a source block is valid before writing only the valid back to the new block. This validity check may itself involve reading parts of a mapping table which may be cached in local random access memory (RAM) or held in non-volatile memory, such as flash. Retrieval of a portion of the mapping table from non-volatile memory is significantly more costly in time and therefore can reduce SSD performance (if garbage collection is done in foreground). In certain SSDs, however, the size of the RAM cache available for storing mapping table information may be significantly smaller than the size of the mapping table and thus garbage collection performance may decrease with smaller RAM cache sizes.